引言

昨天，我們完成一個簡單的粒子系統，具備了視覺化界面。接下來，讓我們植入排序演算法吧！相信大家也不陌生，就是一種把無序的數列按大小順序排列的方法，我們可以用長條圖來視覺化，寬度固定，高度則表示數值大小。

粒子系統架構

延續自系列文：A2 腳步踩穩囉：啟動工廠模式下的 Canvas Transition 動畫

現在，讓我們拓展粒子系統，增加柱子類型的牆壁，作為演算法的視覺化，這裡，我們用到先前文章設計的動畫類 Path，來處理漸進動畫：

class ParticleSystem{
    constructor(width, height){
        this.sort = new SortAlgorithm();
        //......
    }
    createColumn(x, y, width, height){
        const path = new Path(x, y);
        const column = {x, y, width, height, path};
        return column;
    }
    update(){
        this.sort.update(this.column);
        this.balls.forEach((ball) => {
            this.columns.forEach((column) => {
                this.handleColumnCollision(ball, column);
            });
        });
    }
    render(ctx){
        this.columns.forEach((column) => {
            drawColumn(column);
        })
    }
}

因此，在檢測碰撞的時候，我們用 pointX 和 pointY 來取得當下位置，同時，因為柱子是有高度和寬度的，所以要分別用四個邊界來處理。這裡我們也簡化問題，不考慮柱子的旋轉，就不需要計算三角函數：

handleColumnCollision(ball, column) {
    // 取得邊界座標
    const columnTop = column.path.pointY - column.height;
    const columnBottom = column.path.pointY;
    const columnLeft = column.path.pointX - column.width / 2;
    const columnRight = column.path.pointX + column.width / 2;

    // 計算球體與柱子邊界的重疊量
    const overlapX = Math.min(ball.x + ball.r - columnLeft, columnRight - ball.x + ball.r);
    const overlapY = Math.min(ball.y + ball.r - columnTop, columnBottom - ball.y + ball.r);
    
    // 重疊量小於 0 表示沒有碰撞
    if(overlapX < 0 || overlapY < 0) return;

    // 確定碰撞位置並計算反彈
    if (overlapX < overlapY) {
        // 碰撞發生在左右兩側
        ball.vx = -ball.vx * this.friction;
        if (ball.x < column.path.pointX) {
            ball.x = columnLeft - ball.r;
        } else {
            ball.x = columnRight + ball.r;
        }
    } else {
        // 碰撞發生在上下兩側
        ball.vy = -ball.vy * this.friction;
        if (ball.y < column.path.pointY) {
            ball.y = columnTop - ball.r;
        } else {
            ball.y = columnBottom + ball.r;
        }
    }
}

演算法架構

在排序方面，我們用的是逐禎逐步執行的架構，這種架構允許精確控制排序的進行過程。我們需要兩個參數做狀態管理，一個用來判斷排序的開始（isSorting），另一個用來判斷排序的結束（isStoping）。這樣做的好處是，允許在外部控制逐步執行，並根據狀態輸出不同訊息。

class SortAlgorithm{
    constructor(){
        this.sortFunction = function(){};
        this.isSorting = false;
        this.isStoping = false;
    }
    start(name, columns){
        this.send(name + " is processing");
        this.sortFunction = this[name];
        this.timesEveryFrame = 10:
        this.isSorting = true;
        this[name + "Setting"](columns);
    }
    update(columns){
        if(!this.isSorting) return;

        this.times = this.timesEveryFrame;
        while(this.times--){
            const isStoping = this.sortFunction(columns);
            if(isStoping === true){
                [this.isStoping, this.times] = [true, 0];
                const message = this.sortFunction.name + " is done.";
                this.send(message);
            }
        }

        if(this.isStoping){
            this.isSorting = false;
            this.isStoping = false;
        }
    }
    setStepByStep(){
        this.isSorting = true;
        this.isStoping = true;
    }
}

• sortFunction：用來動態指派不同的排序方法
• timesEveryFrame：指派每禎執行的最大次數
• this[name + "Setting"]：初始化排序參數
• isStoping：除了外部控制項，內部也會在每次排序後回傳，來決定是否停止

透過將狀態管理設定為既要開始、又要結束，我們能夠提供使用者按鈕，用來執行下一步，更清楚呈現排序過程：

// 控制介面
const createPhysic = function(){
    this.stepByStep = () => {
        this.system.sort.setStepByStep();
    }
    this.start = (ID) => {
        this.system.sort.start(ID, this.system.columns);
    }
}
const physic = new createPhysic();
export default physic;

// React 元件
<button onClick={physic.stepByStep} id="stepByStep">一步一步來</button> 

至於，到底怎麼拆解迴圈，讓它逐步執行，請允許我賣個關子，明天，娓娓道來！

動畫

在這裡，我們準備一個簡單有效的靜態方法，在排序動畫最重要的就是交換，首先，將表示數值的高度進行交換，然後再把 (x, y) 座標交換。這樣，可以保證長條圖不變，接下來，將動畫物件的路徑設置回原點，這樣就成功交換囉！

class SortAlgorithm{
    static swapColumn(a, b, frame){
        [a.height, b.height] = [b.height, a.height];
        [a.path.pointX, b.path.pointX] = [b.path.pointX, a.path.pointX];
        [a.path.pointY, b.path.pointY] = [b.path.pointY, a.path.pointY];
        a.path.NewTarget(a.x, a.y, frame);
        b.path.NewTarget(b.x, b.y, frame);
    }
}

• height：高度的變化代表數值的交換，這是演算法的核心部分
• NewTarget：座標交換和路徑更新，是視覺化的核心部分

咦？這樣就結束了嗎？沒錯！因為當初我們設計動畫類時，有給它倒數計時，假如設置為 60 禎，就會在一秒內自動完成動畫。不過，興許你會認為這樣的做法不嚴謹，因此，我也有準備一個手動操作的版本：

手動呼叫 NextFrame

首先註解掉自動觸發機制：

class Path extends PathConfig{
    NextFrame = function(){
        // ......
        this.pointX+= (a * linear + b * easein + c * easeout) * dX;
        this.pointY+= (a * linear + b * easein + c * easeout) * dY;
        // this.ID = requestAnimationFrame(this.NextFrame);  
    }//.bind(this);
}

接著，在粒子系統中，碰撞檢測前，要觸發動畫的下一禎：

import Path from './path.js'
class ParticleSystem{
    update(){
        this.columns.forEach((column) => {
            if(column.path instanceof Path){
                column.path.NextFrame();
            }
        })
        //...碰撞檢測
    }
}

• 雖然也能用 proto.constructor.name 來檢查型別，但較為繁瑣。
• 整理來說，我個人比較不喜歡這種作法，因為動畫物件一變多，就容易忘記(X)步驟複雜一出錯(O)導致動畫不會動。

起舞吧！華爾滋

眾所周知，跳舞的時候會頻繁的交換位置，如果我們只是左右交換，那就顯得很普通，既然我們都是兩兩一組進行交換，為何不讓他們起舞呢？

曲線路徑

先前，我們在設計動畫類 Path 的時候，是採用線性路徑的方式，那是因為當時要追蹤的是滑鼠的座標，滑鼠跑來跑去，本來看著就像曲線。但要怎麼實現一個曲線呢？

讓我們簡化問題，既然排序演算是左右交換，Y座標通常不變，那我們就提供一個虛擬 z 軸的跳躍算法，讓它跳起來就好囉!這樣就能輕鬆實現曲線，而不用製作像貝茲曲線那樣，有多個控制項的複雜動畫了。

class Path extends PathConfig{
    getLeap(){
        return super.getLeap();
    }
    NextFrame = function(){
        //......
        const [d, e, f] = this.getLeap();
        this.z+= (d * linear + e * easein + f * easeout) * dX / 5;
    }
}

繪製柱子(10/12補充)

除了透過 z 軸讓柱子跳起來之外，還可以添加漸層效果，將高度作為梯度來取得顏色，這樣一來排列整齊時就會看到平滑的漸層。

function mix(x, from, to){
    return from + x * (to - from);
}
function drawColumn(column){
    const {pointX, pointY, z, timer, period} = column.path;
    
    ctx.beginPath();
    ctx.moveTo(pointX, pointY + z);
    ctx.lineTo(pointX, pointY + z - column.height);
    
    const c = column.height / column.maxHeight;
    const t = 1 - column.path.timer / column.path.period * 0.5;
    const r = mix(t, 255, mix(c, 246, 195));
    const g = mix(t, 100, mix(c, 211, 160));
    const b = mix(t, 100, mix(c, 71, 133));
    ctx.strokeStyle = 'rgba(' + r + ',' + g + ',' + b + ',' + 1 + ')';
    ctx.lineWidth = column.width;
    ctx.stroke();
}

另一方面，將動畫的倒數計時 timer 作為顏色的其中一個控制項，這樣就能在視覺上呈現＂正在＂排序的對象，然後隨著計時歸零（動畫結束），顏色回歸正常。

結論

在這篇文章中，我們透過簡單且有效的粒子系統和排序演算法，展示了如何將動態視覺化與演算法結合。我們從基礎的長條圖視覺化開始，逐步加入動態效果，並針對排序中的交換過程進行了動畫化處理。在此過程中，靜態與手動呼叫的 NextFrame 機制分別提供了不同的控制方式，讓我們能夠精確掌控動畫的執行。

這個框架讓我們能夠在外部控制演算法的步驟，並有效地視覺化過程，特別是在逐步執行的過程中，每一個數值交換和座標變更都能被清晰地展示。這種設計不僅使視覺化動畫的流程更具條理，也讓開發者在處理複雜的演算法動畫時更加靈活。